package 剑指offer;

public class _63股票的最大利润 {
    /**
     * 状态定义：设动态规划列表dp, dp[i] 代表以 prices[i] 为结尾的子数组的最大利润
     * 转移方程：dp[i] = max(dp[i-1], prices[i]-min(prices[0:i]))
     * 初始状态：dp[0] = 0
     * 返回值：dp[n-1], 其中n为dp列表长度
     */
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }

}
